package niuke;

import java.util.*;

public class niuKeMain7 {
    public boolean wordBreak(String s, Set<String> dict) {
        boolean[] canBreak=new boolean[s.length()+1];
        canBreak[0]=true;
        for (int i = 0; i <=s.length(); i++) {
            for (int j = 0; j < i; j++) {
                if (canBreak[j]&&dict.contains(s.substring(j,i))){
                    canBreak[i]=true;
                    break;
                }
            }
        }
        return canBreak[s.length()];
    }
    public int minimumTotal1(ArrayList<ArrayList<Integer>> triangle) {
        if (triangle.isEmpty()){
            return 0;
        }
        List<List<Integer>> min=new ArrayList<>();
        for (int i = 0; i < triangle.size(); i++) {
            min.add(new ArrayList<>());
        }
        min.get(0).add(triangle.get(0).get(0));
        for (int i = 1; i < triangle.size(); i++) {
            int sum=0;
            for (int j = 0; j <=i; j++) {
                if (j==0){
                    sum=min.get(i-1).get(0);
                }else if (j==i){
                    sum=min.get(i-1).get(j-1);
                }else {
                    sum=Math.min(min.get(i-1).get(j),min.get(i-1).get(j-1));
                }
                min.get(i).add(sum+triangle.get(i).get(j));
            }
        }
        int size= triangle.size();
        int a= min.get(size - 1).get(0);
        for (int i = 1; i < size; i++) {
            a=Math.min(a,min.get(size-1).get(i));
        }
        return a;
    }
    public int minimumTotal(ArrayList<ArrayList<Integer>> triangle) {
        if (triangle.isEmpty()){
            return 0;
        }
        List<List<Integer>> min=new ArrayList<>(triangle);
        for (int i = triangle.size()-2; i >=0; i--) {
            for (int j = 0; j <=i; j++) {
                int cursum=Math.min(triangle.get(i+1).get(j),triangle.get(i+1).get(j+1))+ triangle.get(i).get(j);
                min.get(i).set(j,cursum);
            }
        }
        return min.get(0).get(0);
    }
    public int uniquePaths (int m, int n) {
        // write code here
        int array[][]=new int[m][n];
        for (int i = 0; i < m; i++) {
            array[i][0]=1;
        }
        for (int i = 0; i < n; i++) {
            array[0][i]=1;
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                array[i][j]=array[i][j-1]+array[i-1][j];
            }
        }
        return array[m-1][n-1];
    }
    public int minPathSum (int[][] grid) {
        // write code here
        int row= grid.length;
        int col=grid[0].length;
        for (int i = 1; i < col; i++) {
            grid[0][i]=grid[0][i]+grid[0][i-1];
        }
        for (int i = 1; i < row; i++) {
            grid[i][0]=grid[i][0]+grid[i-1][0];
        }
        for (int i = 1; i < row; i++) {
            for (int j = 1; j < col; j++) {
                grid[i][j]=Math.min(grid[i-1][j],grid[i][j-1])+grid[i][j];
            }
        }
        return grid[row-1][col-1];
    }
    public int backPackII(int m, int[] A, int[] V) {
        // write your code here
        int n=A.length;
        int[][] maxValue=new int[n+1][m+1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (A[i-1]<=j){
                    maxValue[i][j]=Math.max(maxValue[i-1][j],maxValue[i-1][j-A[i-1]]+V[i-1]);
                }
                else {
                    maxValue[i][j]=maxValue[i-1][j];
                }
            }
        }
        return maxValue[n][m];
    }
}
